When multiple job processes are served by a single scheduler, the queueingdelays of one process are often affected by the others, resulting in a timingside channel that leaks the arrival pattern of one process to the others. Inthis work, we study such a timing side channel between a regular user and amalicious attacker. Utilizing Shannon's mutual information as a measure ofinformation leakage between the user and attacker, we analyzeprivacy-preserving behaviors of common work-conserving schedulers. We find thatthe attacker can always learn perfectly the user's arrival process in alongest-queue-first (LQF) scheduler. When the user's job arrival rate is verylow (near zero), first-come-first-serve (FCFS) and round robin schedulers bothcompletely reveal the user's arrival pattern. The near-complete informationleakage in the low-rate traffic region is proven to be reduced by half in awork-conserving version of TDMA (WC-TDMA) scheduler, which turns out to beprivacy-optimal in the class of deterministic-working-conserving (det-WC)schedulers, according to a universal lower bound on information leakage wederive for all det-WC schedulers.
展开▼
